// Package day_03_linklist fisrt_cycle_lc_142_mid
// @Title day_03_linklist
// @Description  p判断链表有没有环，有就返回入环节点，没有就返回nil
// @Author  == 琳琳也叫王木木 ==  2021/8/30 17:36
// @Create  2021/8/30 17:36
package day_03_linklist

/**
这道题记住公式就行了，快2慢1，相遇后，快到起点，慢不变，两个同频到相遇，即可 这种题目记住公式，多coding，练出感觉
*/

// FirstInCycle 返回链表第一个入环节点
func FirstInCycle(head *ListNode) *ListNode {
	// 只有一个节点或者一个节点都没有 注定没有环
	if head == nil || head.Next == nil {
		return nil
	}
	fast, slow := head, head
	for true {
		if fast.Next == nil || fast == nil {
			return nil
		}
		fast, slow = fast.Next.Next, slow.Next
		if fast == slow {
			break
		}
	}
	fast = head
	for fast != slow {
		fast, slow = fast.Next, slow.Next
	}
	return fast
}
